W4. Нижняя оценка для сортировок на сравнениях, counting sort, radix sort, bucket sort
1. Краткое содержание
1.1 Нижняя оценка для сортировки на сравнениях (comparison-based sorting)
Один из базовых фактов информатики: алгоритмы сортировки, основанные только на сравнениях элементов, в худшем случае не могут быть быстрее \(\Omega(n \log n)\). Это не «инженерное» ограничение, а математический барьер: как бы ни был устроен алгоритм, если все решения принимаются через сравнения пар элементов, нужно сделать не меньше \(\Omega(n \log n)\) сравнений.
1.1.1 Ключевые идеи про сортировку
Прежде чем доказывать нижнюю оценку, полезно вспомнить «ландшафт» алгоритмов сортировки:
- Квадратичные сортировки на малых \(n\) часто очень быстрые: insertion sort и selection sort работают за \(O(n^2)\). Это звучит медленно, но у таких методов часто отличные константы (constant factors) за счёт простых циклов и дружелюбного к кэшу доступа к памяти. На очень маленьких массивах (типично \(n < 20\)) insertion sort нередко обгоняет «тяжёлые» \(O(n \log n)\)-алгоритмы. Поэтому в промышленных сортировках на маленьких подмассивах часто вызывают именно insertion sort.
- Сортировки на сравнениях имеют нижнюю оценку: в общем случае сортировка «только сравнениями» не укладывается быстрее \(\Omega(n \log n)\). Речь именно о классе алгоритмов, где все решения следуют из сравнений вида «\(A[i] \le A[j]\)?».
- Особые предпосылки дают линейное время: если о данных известно больше (например, узкий диапазон значений), иногда можно обойти барьер \(\Omega(n \log n)\). Эта лекция про алгоритмы сортировки за линейное время (linear-time sorting).
1.1.2 Модель дерева решений (decision tree)
Чтобы понять, почему сравнительной сортировке нужно \(\Omega(n \log n)\) сравнений, используют формализм дерева решений (decision tree):
Decision tree — это бинарное дерево, кодирующее выполнение сравнительного алгоритма сортировки:
- Внутренние узлы (internal nodes) — сравнения (например, «\(A[i] \le A[j]\)?»). У каждого внутреннего узла два ребёнка: ветка «истина» и ветка «ложь».
- Листья (leaves) — исходы выполнения; в модели сортировки удобно думать, что лист соответствует тому порядку, который алгоритм «вывел» после серии сравнений.
- Пути от корня к листу — возможные трассировки: последовательность сравнений до финального результата.
Пример: для трёх элементов \(\langle a_1, a_2, a_3 \rangle\) дерево может начинаться с сравнения \(a_1\) и \(a_2\), затем по ответам уточняется, какая из \(3! = 6\) перестановок соответствует входу; в листьях — шесть возможных полных порядков (total orders) на тройке.
Высота дерева — это число сравнений в худшем случае (worst-case number of comparisons): длина самого длинного пути от корня до листа.
Для любого алгоритма сортировки на входе размера \(n\):
- должно быть не меньше \(n!\) различных листьев (хотя бы по одному на каждую перестановку, которую алгоритм должен различать);
- у бинарного дерева высоты \(h\) не больше \(2^h\) листьев;
- значит \(2^h \ge n!\), откуда \(h \ge \log_2(n!)\).
1.1.3 Вывод нижней оценки
Нужно оценить \(\log_2(n!)\) снизу:
\[h \ge \log_2(n!) = \sum_{i=1}^{n} \log_2(i)\]
Оценка суммы:
\[\sum_{i=1}^{n} \log_2(i) \ge \sum_{i=n/2}^{n} \log_2(i) \ge \sum_{i=n/2}^{n} \log_2(n/2) = \frac{n}{2} \log_2(n/2)\]
\[= \frac{n}{2} (\log_2 n - 1) = \frac{n}{2} \log_2 n - \frac{n}{2} = \Omega(n \log n)\]
Вывод: любой comparison-based алгоритм сортировки в худшем случае делает не меньше \(\Omega(n \log n)\) сравнений.
1.2 Counting sort
Counting sort — алгоритм за время \(\Theta(n+k)\), когда ключи — целые числа из небольшого известного диапазона. Вместо сравнений он считает частоты значений и по ним восстанавливает отсортированный массив.
1.2.1 Предположение и базовая идея
Предположение: элементы — целые в диапазоне \([0, k-1]\) для параметра \(k\). Если диапазон «широкий», иногда его удаётся нормализовать (сдвиг/масштаб), чтобы свести задачу к виду, удобному для counting sort.
Основная идея:
- Подсчёт частот (count frequencies): массив \(C\), где \(C[i]\) — сколько элементов равны \(i\).
- Префиксные суммы (cumulative counts): преобразовать \(C\) так, чтобы \(C[i]\) хранило число элементов \(\le i\) — по этим значениям удобно ставить элементы на финальные позиции.
- Расстановка (place elements): пройти вход и перенести каждый элемент на «его» место по префиксным счётчикам, уменьшая счётчики, чтобы корректно обработать дубликаты.
Плюс префиксных сумм — сохранение устойчивости (stability): равные ключи остаются во взаимном порядке, как во входе.
1.2.2 Наивный вариант
Самая простая схема: посчитать и выписать значения подряд:
- \(C[i]\) = число элементов, равных \(i\);
- пройти значения от \(0\) до \(k-1\);
- записать в выход \(C[i]\) копий числа \(i\).
Время \(\Theta(n+k)\); относительный порядок равных элементов при такой записи определяется порядком значений \(0,\ldots,k-1\), а не обязательно исходным порядком во входе — для записей со спутниками (satellite data) нужна устойчивая схема ниже.
1.2.3 Устойчивый вариант с префиксными суммами
Когда важна stability или нужна аккуратная расстановка по индексам:
- Частоты: \(C[i]\) = число элементов, равных \(i\).
- Префикс: \(C[i] \leftarrow C[i] + C[i-1]\); тогда \(C[i]\) — индекс последнего места для значения \(i\) в выходе (в одной из стандартных реализаций).
- Обход справа налево (backward traversal): идти по входу с конца; для элемента со значением \(v\) положить его в позицию \(C[v]\) выхода и выполнить \(C[v] \leftarrow C[v] - 1\).
Зачем справа налево? Если обрабатывать одинаковые значения с конца входа, в выходе они попадут в том же относительном порядке, что и во входе — это и есть stable counting sort.
Пример: вход \([2, 5, 3, 0, 2, 3, 0, 3]\), значения в \([0, 5]\).
- Частоты: \(C = [2, 0, 2, 3, 0, 1]\)
- Префикс: \(C = [2, 2, 4, 7, 7, 8]\)
- Справа налево: например, тройка в позиции 7 идёт в \(C[3]=7\), затем \(C[3]=6\); ноль в позиции 6 идёт в \(C[0]=2\), затем \(C[0]=1\); и так далее.
- Выход: \([0, 0, 2, 2, 3, 3, 3, 5]\)
1.2.4 Время и память
- Время: \(\Theta(n+k)\) — подсчёт \(\Theta(n)\), префикс \(\Theta(k)\), расстановка \(\Theta(n)\).
- Память: \(\Theta(n+k)\) — выход и массив счётчиков.
Когда counting sort уместен? Когда \(k\) сопоставимо с \(n\) или мало. Если \(k \approx n\), по порядку величины сравнимо с \(O(n\log n)\). Если \(k \gg n\), counting sort может проигрывать, например, merge sort.
1.3 Radix sort
Radix sort переносит идею counting sort на «многоразрядные» ключи: сортирует по цифрам (digits) слева направо в смысле значимости, но проходы делают от младшего разряда к старшему (least significant digit, LSD). Ключевой факт: если старшие разряды уже упорядочены устойчивой сортировкой по младшим проходам, очередной устойчивый проход по более старшей цифре не ломает порядок по уже «выстроенным» младшим позициям.
1.3.1 Постановка
Вход: числа из \(d\) «цифр», каждая цифра в \([0, k-1]\).
Идея: \(d\) проходов стабильной сортировки:
- по цифре \(d\) (младшей);
- затем по \(d-1\);
- …
- по цифре \(1\) (старшей).
После \(d\) проходов массив отсортирован по полному ключу.
1.3.2 Почему это работает
Утверждение: после сортировки по последним \(i\) цифрам массив упорядован лексикографически по этим \(i\) цифрам.
Набросок доказательства:
- после первого (младшего) прохода числа упорядованы по последней цифре;
- каждый следующий проход — stable sort по более старшей позиции: внутри блока с одинаковой текущей цифрой сохраняется порядок по уже обработанным младшим разрядам.
Пример: \([329, 457, 657, 839, 436, 720, 355]\) (три десятичных разряда, цифры в \([0,9]\)).
- По единицам: \([720, 355, 436, 457, 657, 329, 839]\)
- По десяткам (stable): \([720, 329, 436, 839, 355, 457, 657]\)
- По сотням (stable): \([329, 355, 436, 457, 657, 720, 839]\)
Результат: полностью отсортированный массив.
1.3.3 Временная сложность
Если на каждом проходе использовать counting sort:
- \(d\) проходов, на каждом — \(n\) элементов и \(k\) значений цифры;
- время прохода: \(\Theta(n+k)\);
- всего: \(\Theta(d(n+k))\).
Частный случай — \(b\)-битные двоичные числа:
- \(d=b\) «цифр» в основании 2, \(k=2\);
- время \(\Theta(b(n+2))=\Theta(bn)\) для чисел в \([0, 2^b-1]\).
Ускорение: обрабатывать блоки по \(r\) бит за раз; тогда \(d=b/r\), а значений «цифры» \(k=2^r\):
\[T(n) = \Theta\left(\frac{b}{r}(n + 2^r)\right)\]
Часто выбирают \(r \approx \log n\), балансируя число проходов и стоимость counting sort на проход.
1.4 Bucket sort
Bucket sort — ещё один способ получить среднее время порядка \(\Theta(n)\) при равномерном распределении (uniform distribution) ключей на известном интервале (часто нормируют к \([0, 1)\)). Диапазон режут на корзины (buckets), элементы раскладывают по корзинам, внутри каждой сортируют (часто insertion sort), затем конкатенируют.
1.4.1 Предположение и алгоритм
Предположение: \(n\) чисел независимо и равномерно на \([0, 1)\) (обобщение на \([a,b)\) — линейным масштабированием).
Алгоритм:
- \(n\) корзин: отрезки \([0, 1/n)\), \([1/n, 2/n)\), …, \([(n-1)/n, 1)\).
- Раскладка: элемент \(x\) кладём в корзину с индексом \(\lfloor n \cdot x \rfloor\).
- Сортировка внутри корзин: любым методом (часто insertion sort на маленьких списках).
- Склейка: корзины 0, 1, … подряд.
Зачем нужна равномерность: тогда ожидаемый размер корзины \(O(1)\), и внутренняя сортировка дешева в среднем.
1.4.2 Анализ сложности
Пусть \(n_i\) — число элементов в корзине \(i\).
Суммарное время (с insertion sort в корзинах):
\[T(n) = \Theta(n) + \sum_{i=1}^{n} O(n_i^2)\]
где \(\Theta(n)\) — подготовка и раскладка, \(O(n_i^2)\) — сортировка \(i\)-й корзины.
Ожидаемое время при равномерности на \([0,1)\) и \(n\) корзинах:
Вероятность попасть в фиксированную корзину у каждого элемента \(1/n\), поэтому \(n_i\) — \(\mathrm{Binomial}(n, 1/n)\):
\[E[n_i] = 1, \quad E[n_i^2] = 2 - 1/n\]
Отсюда
\[E[T(n)] = \Theta(n) + \sum_{i=1}^{n} O(E[n_i^2]) = \Theta(n) + n \cdot O(2 - 1/n) = \Theta(n)\]
Почему именно \(n\) корзин? Слишком мало корзин — переполнение и рост \(n_i^2\); слишком много — лишние пустые корзины. \(n\) корзин на \(n\) элементов — типичный компромисс: ожидаемый размер \(O(1)\), ожидаемое суммарное время \(\Theta(n)\).
1.4.3 Худший случай
Если все элементы попали в одну корзину, внутри неё insertion sort на всех \(n\):
\[T_{\text{worst}}(n) = \Theta(n^2)\]
Так бывает при сильном отклонении от равномерности или «патологическом» входе.
1.5 Сравнение алгоритмов линейного времени
У трёх подходов разные сильные и слабые стороны:
| Алгоритм | Время | Память | Предположение | Stable | Примечание |
|---|---|---|---|---|---|
| Counting sort | \(\Theta(n + k)\) | \(\Theta(n + k)\) | Узкий целочисленный диапазон \([0, k-1]\) | да | Разумен при \(k = O(n)\) |
| Radix sort | \(\Theta(d(n + k))\) | \(\Theta(n + k)\) | Многоразрядные ключи | да (при stable под-сортировке) | Удобен для длинных целых / строк с фикс. алфавитом |
| Bucket sort | \(\Theta(n)\) в среднем | \(\Theta(n)\) | Примерно равномерное распределение на отрезке | да | Худший случай \(\Theta(n^2)\) |
Как выбирать:
- Counting sort — малые целые в известном диапазоне (оценки 0–100, частоты символов и т.п.).
- Radix sort — фиксированная ширина представления (биты/байты), строки одинаковой длины или с дополнением.
- Bucket sort — известна хорошая «геометрия» распределения; нужна простая средняя линейность.
- Comparison-based (merge sort, quicksort, …) — когда нужны гарантии без сильных предположений о ключах или когда линейные методы неприменимы.
2. Определения
- Comparison-based sorting: сортировка, в которой все ветвления следуют из сравнений пар элементов (например, \(A[i] \le A[j]\)).
- Decision tree: бинарное дерево, моделирующее сравнительную сортировку: внутренние узлы — сравнения, листья — исходы (упорядочивания).
- Lower bound: доказанный снизу минимум числа операций в худшем случае для класса алгоритмов (здесь \(\Omega(n \log n)\) сравнений).
- Counting sort: линейно-временной (относительно \(n+k\)) подсчёт частот целых ключей в \([0,k-1]\) и восстановление порядка.
- Stable sort: сортировка, сохраняющая относительный порядок элементов с равными ключами.
- Cumulative count array: после префиксных сумм в counting sort — массив числа элементов \(\le\) данного значения (или эквивалентная интерпретация для расстановки).
- Radix sort: поразрядная сортировка, обычно LSD, со stable под-сортировкой на каждом разряде.
- Digit (radix sort): одна позиция разряда, по которой делается отдельный проход.
- Least significant digit (LSD): младший разряд; в стандартном radix sort сортировка начинается с него.
- Bucket sort: разбиение диапазона на корзины, локальная сортировка, склейка; средний случай часто линейный при равномерности.
- Bucket: подинтервал диапазона, накапливающий подмножество входа перед локальной сортировкой.
- Uniform distribution: модель, в которой плотность на отрезке постоянна; типичное предположение для среднего анализа bucket sort.
- Amortized analysis: оценка средней стоимости операции в длинной серии, с учётом редких дорогих шагов.
- In-place sorting: сортировка с \(O(1)\) или \(O(\log n)\) доп. памяти (не считая входа/выхода по соглашению о модели).
- Linear-time sorting: сортировка за \(O(n)\) или \(\Theta(n+k)\) при дополнительных предположениях о ключах.
3. Формулы
- Нижняя оценка (decision tree): \(2^h \ge n! \implies h \ge \log_2(n!) = \Omega(n \log n)\)
- Оценка \(\log_2(n!)\) снизу: \(\log_2(n!) \ge \sum_{i=n/2}^{n} \log_2(n/2) = \frac{n}{2} \log_2(n/2) = \Omega(n \log n)\)
- Counting sort, время: \(\Theta(n + k)\)
- Counting sort, память: \(\Theta(n + k)\)
- Radix sort (общий вид): \(\Theta(d(n + k))\)
- Radix sort (битовый): \(\Theta(b \cdot n)\) для \(b\) бит при под-сортировке с \(k=2\)
- Radix sort, блоки по \(r\) бит: \(\Theta\left(\frac{b}{r}(n + 2^r)\right)\); часто \(r \approx \log n\)
- Индекс корзины: \(\text{bucket} = \lfloor n \cdot x \rfloor\) для \(x \in [0, 1)\)
- Bucket sort, среднее: \(\Theta(n)\) при равномерности и \(n\) корзинах
- Bucket sort, худшее: \(\Theta(n^2)\), если одна корзина содержит все элементы
- Ожидаемый размер корзины: \(E[n_i] = 1\) при \(n\) элементах и \(n\) равных интервалах
- Ожидаемая стоимость insertion sort в корзине: \(E[n_i^2] = 2 - 1/n\)
4. Примеры
4.1. Применить counting sort (Набор задач 4, Задание 1)
Примените counting sort к массиву ключей и связанных данных:
Данные | A | O | S | R | Y | E | O | A | U | W | M | E | E |
Покажите:
- вспомогательный массив до заполнения выхода;
- вспомогательный массив после завершения алгоритма;
- итоговый выход: ключи и данные.
Нажмите, чтобы увидеть решение
Ключевая идея: устойчивый counting sort сохраняет относительный порядок записей с равными ключами.
Вход: ключи \([3, 1, 6, 3, 0, 3, 6, 3, 1, 4, 6, 4, 6]\), данные \([A, O, S, R, Y, E, O, A, U, W, M, E, E]\).
Диапазон: \(0\)–\(6\) (то есть \(k = 7\)).
Шаг 1: частоты
Частота | 1 | 2 | 0 | 4 | 2 | 0 | 4 |
Массив \(C\) до заполнения выхода (чистые частоты):
\[C = [1, 2, 0, 4, 2, 0, 4]\]
Шаг 2: префиксные суммы
Префикс | 1 | 3 | 3 | 7 | 9 | 9 | 13 |
Массив \(C\) после вычисления префикса (перед расстановкой; далее при расстановке индексы уменьшаются):
\[C = [1, 3, 3, 7, 9, 9, 13]\]
Шаг 3: расстановка справа налево
Для позиции \(i\) справа налево: ключ \(v = \text{keys}[i]\), кладём запись в позицию \(C[v]\) выхода, затем \(C[v] \leftarrow C[v]-1\).
| Шаг | \(i\) | Ключ | Данные | \(C[\text{key}]\) | Позиция выхода | Обновлённый \(C\) |
|---|---|---|---|---|---|---|
| 1 | 12 | 6 | E | 13 | 13 | \([1, 3, 3, 7, 9, 9, 12]\) |
| 2 | 11 | 4 | E | 9 | 9 | \([1, 3, 3, 7, 8, 9, 12]\) |
| 3 | 10 | 6 | M | 12 | 12 | \([1, 3, 3, 7, 8, 9, 11]\) |
| 4 | 9 | 4 | W | 8 | 8 | \([1, 3, 3, 7, 7, 9, 11]\) |
| 5 | 8 | 1 | U | 3 | 3 | \([1, 2, 3, 7, 7, 9, 11]\) |
| 6 | 7 | 3 | A | 7 | 7 | \([1, 2, 3, 6, 7, 9, 11]\) |
| 7 | 6 | 6 | O | 11 | 11 | \([1, 2, 3, 6, 7, 9, 10]\) |
| 8 | 5 | 3 | E | 6 | 6 | \([1, 2, 3, 5, 7, 9, 10]\) |
| 9 | 4 | 0 | Y | 1 | 1 | \([0, 2, 3, 5, 7, 9, 10]\) |
| 10 | 3 | 3 | R | 5 | 5 | \([0, 2, 3, 4, 7, 9, 10]\) |
| 11 | 2 | 6 | S | 10 | 10 | \([0, 2, 3, 4, 7, 9, 9]\) |
| 12 | 1 | 1 | O | 2 | 2 | \([0, 1, 3, 4, 7, 9, 9]\) |
| 13 | 0 | 3 | A | 4 | 4 | \([0, 1, 2, 4, 7, 9, 9]\) |
Итог (ключи и данные по возрастанию ключа):
Ключ | 0 | 1 | 1 | 3 | 3 | 3 | 3 | 4 | 4 | 6 | 6 | 6 | 6 |
Данные | Y | O | U | A | R | E | A | W | E | S | O | M | E |
Ответ:
- До заполнения выхода: \(C = [1, 2, 0, 4, 2, 0, 4]\) (частоты).
- После префикса (перед/во время расстановки): \(C = [1, 3, 3, 7, 9, 9, 13]\) (префиксные суммы; в процессе ячейки уменьшаются).
- Выход: ключи \([0, 1, 1, 3, 3, 3, 3, 4, 4, 6, 6, 6, 6]\), данные \([Y, O, U, A, R, E, A, W, E, S, O, M, E]\) (stable).
4.2. Сложность radix sort для «программ» (Набор задач 4, Задание 2)
Рассмотрим иерархию:
- каждая program — последовательность не более чем из \(b\) code blocks;
- каждый code block — последовательность не более чем из \(c\) instruction codes;
- каждый instruction code — элемент алфавита размера \(k\).
Оцените worst-case время radix sort для массива из \(n\) program, если code blocks внутри одной позиции сортируют:
(a) insertion sort
(b) merge sort
(c) radix sort (с counting sort по instruction codes)
Сравнение двух instruction codes стоит \(\Theta(1)\), но сравнение двух code blocks или двух program — уже не \(\Theta(1)\).
Нажмите, чтобы увидеть решение
Ключевая идея: внешний radix sort делает \(b\) проходов; на каждом проходе сортируются «столбцы» из \(n\) code blocks; стоимость сравнения блоков — \(\Theta(c)\).
(a) Insertion sort для блоков
- \(b\) проходов по позициям блока.
- На проходе — insertion sort на \(n\) блоках: до \(\Theta(n^2)\) сравнений, каждое сравнение двух блоков — \(\Theta(c)\).
- Один проход: \(\Theta(n^2 c)\); всего \(b\) проходов:
\[\boxed{T(n) = \Theta(n^2 bc)}\]
(b) Merge sort для блоков
- На проходе: \(\Theta(n \log n)\) сравнений × \(\Theta(c)\) за сравнение блоков → \(\Theta(nc \log n)\).
- \(b\) проходов:
\[\boxed{T(n) = \Theta(nbc \log n)}\]
(c) Radix sort по инструкциям внутри блока
- Сортировка одного code block как ключа из \(c\) «разрядов» над алфавитом \(k\): counting sort на каждом разряде даёт \(\Theta(n+k)\) на один проход по всем программам на фиксированной позиции инструкции — в типовой постановке «отсортировать \(n\) блоков по \(j\)-й инструкции» стоимость прохода \(\Theta(n+k)\); \(c\) таких проходов на сортировку столбца блоков: \(\Theta(c(n+k))\).
- Внешних проходов по позициям блока: \(b\).
\[\boxed{T(n) = \Theta(bc(n + k))}\]
Сводка
| Метод | Сложность |
|---|---|
| (a) insertion sort | \(\Theta(n^2bc)\) |
| (b) merge sort | \(\Theta(nbc \log n)\) |
| (c) radix sort | \(\Theta(bc(n + k))\) |
При больших \(n\) вариант (c) выигрывает, если \(k\) умеренное; (b) лучше (a) при больших \(n\).
4.3. Дерево решений для варианта quicksort (Набор задач 4, Задание 3)
Постройте decision tree для варианта quick-sort, где pivot всегда берётся как второй элемент подмассива, для входа размера 4. Ответьте:
- Сколько листьев у дерева?
- Длина кратчайшего пути от корня до листа?
- Длина самого длинного пути от корня до листа?
Нажмите, чтобы увидеть решение
Ключевая идея: decision tree сравнительной сортировки на \(n\) элементах должно различать все \(n!\) входных упорядочений; высота дерева связана с числом сравнений в худшем случае.
(a) Число листьев
Любой корректный comparison-based алгоритм сортировки четырёх различимых элементов должен иметь не меньше \(4! = 24\) листьев (по одному на каждую перестановку как отдельный «исход» различимости).
\[\text{листьев} = 24\]
(b) Кратчайший путь
Нижняя оценка высоты любого бинарного дерева с \(L\) листьями: \(h \ge \lceil \log_2 L \rceil\). Здесь \(L=24\), \(\log_2 24 \approx 4{,}585\), значит не меньше 5 сравнений на некоторых входах в модели, где каждое сравнение — один уровень. Кратчайший путь от корня до какого-то листа не может быть короче этой информационно-теоретической границы для полного различения всех перестановок в худшем случае по дереву; для конкретного варианта quicksort с фиксированным pivot на практике удобно согласовать ответ курса с нижней оценкой \(\lceil \log_2(4!) \rceil = 5\).
Ответ (как в стандартном разборе): кратчайшая длина пути 5.
(c) Самый длинный путь
При неудачных разбиениях (pivot — минимум/максимум в подмассиве) quicksort ведёт себя как \(T(n)=T(n-1)+\Theta(n)\), для \(n=4\) типично получают 6 сравнений на худшей ветке разбиений для данного правила выбора pivot.
Ответ: длина самого длинного пути 6.
Сводка
| Величина | Значение |
|---|---|
| (a) листья | \(24\) |
| (b) кратчайший путь | \(5\) |
| (c) длиннейший путь | \(6\) |
4.4. Доказать \(\Omega(n\log n)\) для сортировки на сравнениях (Лекция 4, Пример 1)
Докажите, что любая comparison-based сортировка в худшем случае требует не меньше \(\Omega(n \log n)\) сравнений.
Нажмите, чтобы увидеть решение
Ключевая идея: модель decision tree: \(\ge n!\) листьев, высота — число сравнений в худшем случае.
Дерево: внутренние узлы — сравнения, листья — различимые исходы; для сортировки нужно различить все перестановки входа — не меньше \(n!\) листьев.
Связь с высотой: в бинарном дереве высоты \(h\) не больше \(2^h\) листьев, значит \(2^h \ge n!\), т.е. \(h \ge \log_2(n!)\).
Оценка \(\log_2(n!)\):
\[\log_2(n!) = \sum_{i=1}^{n} \log_2(i) \ge \sum_{i=n/2}^{n} \log_2(n/2) = \frac{n}{2}\log_2(n/2) = \frac{n}{2}(\log_2 n - 1) = \Omega(n\log n)\]
Вывод: \(T_{\text{worst}}(n) \ge h \ge \log_2(n!) = \Omega(n\log n)\).
Ответ: нижняя оценка \(\Omega(n\log n)\) следует из аргумента с decision tree и оценки суммы логарифмов.
4.5. Radix sort для десятичных чисел (Лекция 4, Пример 2)
Отсортируйте массив \([329, 457, 657, 839, 436, 720, 355]\) radix sort-ом. Покажите массив после сортировки по каждому разряду.
Нажмите, чтобы увидеть решение
Ключевая идея: LSD + stable сортировка на каждом разряде (например, counting sort).
Вход: \([329, 457, 657, 839, 436, 720, 355]\) (три десятичных разряда, цифры \(0\)–\(9\)).
Проход 1 — единицы
- по 0: 720; по 5: 355; по 6: 436; по 7: 457, затем 657 (stable); по 9: 329, затем 839.
После прохода 1: \([720, 355, 436, 457, 657, 329, 839]\)
Проход 2 — десятки
- по 2: 720, 329; по 3: 436, 839; по 5: 355, 457, 657.
После прохода 2: \([720, 329, 436, 839, 355, 457, 657]\)
Проход 3 — сотни
- по 3: 329, 355; по 4: 436, 457; по 6: 657; по 7: 720; по 8: 839.
После прохода 3: \([329, 355, 436, 457, 657, 720, 839]\)
Проверка сложности: \(n=7\), \(d=3\), \(k=10\) → \(\Theta(d(n+k)) = \Theta(3(7+10))\).
Ответ: последовательность после единиц, десятков и сотен — \([329, 355, 436, 457, 657, 720, 839]\).
4.6. Средний случай bucket sort (Лекция 4, Пример 3)
Проанализируйте average-case время bucket sort для \(n\) элементов, равномерно распределённых на \([0,1)\), при \(n\) корзинах и insertion sort внутри каждой корзины.
Нажмите, чтобы увидеть решение
Ключевая идея: \(n_i \sim \mathrm{Binomial}(n, 1/n)\), \(E[n_i^2]=O(1)\), сумма квадратов — \(O(n)\).
- Модель: корзина \(i\) — интервал \([i/n,(i+1)/n)\); индикаторы попадания независимы, \(P(\text{элемент в } i)=1/n\).
- Размер корзины \(X_i\): биномиальное распределение \(\mathrm{Binomial}(n,1/n)\).
- Ожидание: \(E[X_i]=1\).
- Второй момент: \(\mathrm{Var}(X_i)=n\cdot\frac1n(1-\frac1n)=1-\frac1n\), \(E[X_i^2]=\mathrm{Var}+(E[X_i])^2=2-\frac1n\).
- Суммарно: \(E[T(n)]=\Theta(n)+\sum_i O(E[X_i^2])=\Theta(n)+n\cdot O(1)=\Theta(n)\).
- Про выбор \(n\) корзин: при \(m\) корзинах ожидаемая квадратичная стоимость insertion sort даёт вклад порядка \(m\cdot O((n/m)^2)=O(n^2/m)\); баланс у \(m\asymp n\).
Ответ: expected time \(\Theta(n)\) при равномерности на \([0,1)\) и \(n\) корзинах.
4.7. Дерево решений для insertion sort на трёх элементах (Лекция 4, Пример 4)
Постройте decision tree для insertion sort, сортирующего три элемента \(\langle a, b, c\rangle\). Перечислите все листья (итоговые упорядочивания).
Нажмите, чтобы увидеть решение
Ключевая идея: каждый внутренний узел — сравнение, каждый лист — одна из \(3!=6\) линейных упорядоченностей.
Логика insertion sort: сравнить \(a\) и \(b\); затем вставить \(c\) серией сравнений.
Корень: \(a \le b\)?
- Да: известно \(a \le b\). Далее \(b \le c\)?
- Да: \(a \le b \le c\) — лист.
- Нет: \(b > c\); сравнить \(a\) и \(c\):
- \(a \le c\) → лист \(a \le c < b\)
- \(a > c\) → лист \(c < a \le b\)
- Нет: \(b < a\). Далее \(a \le c\)?
- Да: лист \(b < a \le c\)
- Нет: сравнить \(b\) и \(c\):
- \(b \le c\) → лист \(b \le c < a\)
- \(b > c\) → лист \(c < b < a\)
Схема:
a ≤ b?
/ \
ДА НЕТ
/ \
b ≤ c? a ≤ c?
/ \ / \
ДА НЕТ ДА НЕТ
/ \ / \
a≤b≤c a≤c? b<a≤c b≤c?
/ \ / \
a≤c<b c<a≤b b≤c<a c<b<aШесть листьев:
- \(a \le b \le c\)
- \(a \le c < b\)
- \(c < a \le b\)
- \(b < a \le c\)
- \(b \le c < a\)
- \(c < b < a\)
Высота: на длиннейшей ветке три сравнения; \(\lceil \log_2(3!) \rceil = \lceil \log_2 6 \rceil = 3\) — согласуется с нижней оценкой для \(n=3\).
Ответ: 6 листьев — шесть перестановок; длиннейший путь из трёх сравнений.
4.8. Устойчивость radix sort (Лекция 4, Пример 5)
Объясните, почему radix sort устойчив, если под-сортировка на каждом разряде устойчива. Приведите пример.
Нажмите, чтобы увидеть решение
Ключевая идея: stable проходы не переставляют местами элементы с равным текущим разрядом, если они уже были в правильном относительном порядке «по младшим разрядам».
Утверждение: если на каждом разряде используется stable sort, то radix sort в целом stable.
Идея доказательства (индукция по разрядам): после обработки младших \(i\) разрядов относительный порядок записей с одинаковыми младшими \(i\) разрядами корректен; при сортировке по \((i+1)\)-му разряду stable сортировка не меняет порядок внутри групп с одинаковой \((i+1)\)-й цифрой — этот порядок как раз кодирует младшие \(i\) разрядов.
Пример: пары (ключ, данные), ключ — двузначное число.
Вход: \((23, A), (12, B), (23, C), (15, D), (12, E)\)
Проход 1 — единицы (stable** counting sort):**
| Единицы | Записи |
|---|---|
| 2 | \((12,B), (12,E)\) |
| 3 | \((23,A), (23,C)\) |
| 5 | \((15,D)\) |
После прохода 1: \((12,B), (12,E), (23,A), (23,C), (15,D)\)
Проход 2 — десятки:
| Десятки | Записи (в текущем порядке) |
|---|---|
| 1 | \((12,B), (12,E), (15,D)\) |
| 2 | \((23,A), (23,C)\) |
После прохода 2: \((12,B), (12,E), (15,D), (23,A), (23,C)\)
У равных ключей 12 сохранился порядок \(B\) перед \(E\); у 23 — \(A\) перед \(C\).
Ответ: stability на каждом шаге «накапливается» в корректный порядок по всем разрядам.
4.9. Выбор сортировки под данные (Лекция 4, Задание 1)
Для каждого сценария предложите разумный алгоритм и обоснуйте:
- миллион английских слов разной длины;
- миллиард 32-битных беззнаковых целых;
- 100 студентов по оценке 0–100;
- связный список целых произвольной величины.
Нажмите, чтобы увидеть решение
Ключевая идея: сопоставить структуру ключей, память, доступ и предпосылки линейных методов.
(1) Слова переменной длины
Рекомендация: merge sort или quicksort (comparison-based).
Почему: нет компактного \(k\) для counting sort; radix sort потребует выравнивания длины; bucket sort по «равномерности букв» для естественного языка слаб. \(O(n\log n)\) на \(10^6\) — практично.
(2) \(10^9\) целых 32 бита
Рекомендация: radix sort (например, по байтам: \(d=4\), \(k=256\)).
Почему: фиксированная ширина; время порядка \(\Theta(d(n+k))\ll \Theta(n\log n)\) при больших \(n\).
(3) Оценки 0–100
Рекомендация: counting sort.
Почему: \(k=101\), \(n=100\) → \(\Theta(n+k)\) очень мало; удобно обрабатывать повторы stable-вариантом.
(4) Связный список целых
Рекомендация: merge sort для списков.
Почему: нет быстрого произвольного доступа; merge естественно сливает списки за указателями; quicksort/блочные схемы неудобны.
Ответы: (1) merge/quicksort; (2) radix sort; (3) counting sort; (4) merge sort.
4.10. \(\Theta(n)\) для чисел в \([0, n^5-1]\) (Лекция 4, Задание 2)
Покажите, что \(n\) чисел из диапазона \([0, n^5-1]\) можно отсортировать за \(\Theta(n)\). Какой radix и сколько «цифр»?
Нажмите, чтобы увидеть решение
Ключевая идея: представить число в системе счисления с основанием \(n\): нужно \(5\) разрядов, каждый разряд в \([0,n-1]\).
- Любое число \(< n^5\) записывается не более чем пятью «цифрами» в основании \(n\).
- Radix sort: \(d=5\), на каждом проходе counting sort с \(k=n\) → \(\Theta(n+k)=\Theta(n)\) на проход.
- Всего \(\Theta(5n)=\Theta(n)\).
Ответ: основание \(k=n\), число разрядов \(d=5\); время \(\Theta(n)\).
4.11. Переменный radix для битовых чисел (Лекция 4, Задание 3)
Покажите, что \(n\) чисел из \(d\) бит можно отсортировать за \(\Theta\left(\frac{d}{r}(n+2^r)\right)\) при любом \(1\le r\le d\). Какой выбор \(r\) минимизирует выражение (в асимптотическом смысле)?
Нажмите, чтобы увидеть решение
Ключевая идея: группировать по \(r\) бит → «цифра» из \(2^r\) значений; \(\frac{d}{r}\) проходов counting sort за \(\Theta(n+2^r)\) каждый.
\[T(n)=\Theta\left(\frac{d}{r}(n+2^r)\right)\]
Баланс между \(\frac{d}{r}\) и \(2^r\): часто берут \(r\approx \log_2 n\) (если \(r\le d\)), чтобы \(n+2^r=\Theta(n)\) и число проходов \(\Theta(d/\log n)\).
Ответ: формула выше; типичный минимизирующий выбор \(r \asymp \log_2 n\) при ограничениях на \(d\).
4.12. Запросы на отрезке после counting sort (Лекция 4, Задание 4)
Предобработайте массив из \(n\) чисел в диапазоне \([0,k]\) так, чтобы запросы «сколько элементов в \([a,b]\)?» отвечались за \(\Theta(1)\).
Нажмите, чтобы увидеть решение
Ключевая идея: префиксные суммы частот — это массив числа элементов \(\le t\).
- Посчитать частоты \(C[v]\) для каждого \(v\).
- \(C[v]\leftarrow C[v]+C[v-1]\) — теперь \(C[v]\) = число элементов \(\le v\).
- Запрос \([a,b]\) включительно:
\[\text{count} = C[b] - C[a-1]\]
(для \(a=0\) используют \(C[b]\), полагая \(C[-1]=0\)).
Пример: вход \([0,3,0,1,0,0,1,3]\) → частоты \([4,2,0,2]\) → префикс \([4,6,6,8]\); запрос \([1,3]\): \(C[3]-C[0]=8-4=4\).
Сложность: предобработка \(\Theta(n+k)\), запрос \(\Theta(1)\), \(q\) запросов — \(\Theta(n+k+q)\).
Ответ: префикс частот; ответ на отрезок за \(O(1)\) формулой \(C[b]-C[a-1]\).